import org.w3c.dom.CDATASection;

import java.util.PriorityQueue;

public class MySingleList {
    static class ListNode{
        public int val;
        public ListNode next;

        public ListNode(int val) {
            this.val = val;
        }
    }
    public ListNode head;
    //创建一个单链表；
    public void create(){
        ListNode node1=new ListNode(12);
        ListNode node2=new ListNode(23);
        ListNode node3=new ListNode(34);
        ListNode node4=new ListNode(45);
        ListNode node5=new ListNode(56);
        node1.next=node2;
        node2.next=node3;
        node3.next=node4;
        node4.next=node5;
        head=node1;
    }
    //2.打印单链表；
    public void show(){
        ListNode cur=head;
        while(cur!=null){
            System.out.print(cur.val+" ");
            cur=cur.next;
        }
    }
    //3.求单链表长度；
    public int size(){
        ListNode cur=head;
        int count=0;
        while(cur!=null){
            count++;
            cur=cur.next;
        }
        return count;
    }
    //4.头插法：
    public void addFirst(int date){
        ListNode node=new ListNode(date);
        node.next=head;
        head=node;
    }
    //5.尾插法；
    public void addLast(int date){
        ListNode node=new ListNode(date);
        if(head==null){
            head=node;
            return;
        }
        ListNode cur=head;
        while(cur.next!=null){
            cur=cur.next;
        }
        cur.next=node;
    }
    //6.向单链表中某个位置插入某个元素；
    public void set(int index,int date){
        int len=size();
        if(index<0||index>len){
            System.out.println("插入单链表位置不合法");
        }
        if(index==0){
            addFirst(date);
            return;
        }
        if(index==len){
            addLast(date);
            return;
        }
        ListNode cur=searchListNode(index);
        if(cur==null){
            return;
        }
        ListNode node=new ListNode(date);
        node.next=cur.next;
        cur.next=node;
    }
    public ListNode searchListNode(int index){
        int len=size();
        if(index<0||index>len){
            return null;
        }
        int count=0;
        ListNode cur=head;
        while(count!=index-1){
            cur=cur.next;
            count++;
        }
        return cur;
    }
    //7.判断单链表中是否包含某个元素；
    public boolean contains(int date){
        ListNode cur=head;
        if(head==null){
            return false;
        }
        while(cur.next!=null){
            if(cur.val==date){
                return true;
            }
            cur=cur.next;
        }
        return false;
    }
    //8.删除单链表中第一个出现值为key中结点；
    public void remove(int key){
        if(head==null){
            return;
        }
        if(head.val==key){
            head=head.next;
        }
        ListNode prev=findListNode(key);
        if(prev==null){
            System.out.println("没有你要删除的节点");
            return;
        }
        ListNode del=prev.next;
        prev.next=del.next;
    }
    //寻找要删除节点的前一个结点；
    public ListNode findListNode(int key){
        if(head==null){
            return null;
        }
        ListNode prev=head;
        while(prev.next!=null){
            if(prev.next.val==key){
                return prev;
            }
            prev=prev.next;
        }
        return null;
    }
    //9.删除单链表中所有值为key的节点；
    public void removeAllLkey(int key){
        if(head==null){
            return;
        }
        ListNode prev=head;
        ListNode cur=head.next;
        while(cur!=null){
            if(cur.val==key){
                cur=cur.next;
                prev.next=cur;
            }else{
                prev=prev.next;
                cur=cur.next;
            }
        }
        if(head.val==key){
            head=head.next;
        }
    }
    //10.反转单链表；
    //方法一：递归法：
    public ListNode reverseList(ListNode head){
        if(head==null){
            return head;
        }
        if(head.next==null){
            return head;
        }
        ListNode newListNode=reverseList(head.next);
        head.next.next=head;
        head.next=null;
        return newListNode;
    }
    //方法二;
    public ListNode reverseList(){
        ListNode cur=head.next;
        head.next=null;
        while(cur!=null){
            ListNode curN=cur.next;
            cur.next=head;
            head=cur;
            cur=curN;
        }
        return head;
    }
    //打印单链表；进行正确接收反转后的单链表；
    public void show(ListNode head){
        ListNode cur=head;
        while(cur!=null){
            System.out.print(cur.val+" ");
            cur=cur.next;
        }
    }
    //寻找单链表中间节点的值；
    public ListNode middleListNodekey(){
        if(head==null){
            return head;
        }
        if(head.next==null){
            return head;
        }
        ListNode fast=head;
        ListNode slow=head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        return slow;
    }
    //寻找一个单链表中倒数第k个节点的值；
    public ListNode fidnK(int k){
      if(k<0){
          System.out.println("寻找的位置不合法");
          return null;
      }
      ListNode fast=head;
      ListNode slow=head;
      int count=0;
      while(count!=k-1){
          fast=fast.next;
          count++;
      }
      while(fast.next!=null){
          fast=fast.next;
          slow=slow.next;
      }
      return slow;
    }
//给定一个结点值，进行将单链表中比给定值小的放在前面，大的放在后面，
// 并且要求不改变原来单链表的顺序；
    public ListNode partition(int x){
        if(head==null){
            return head;
        }
        ListNode beforeStart=null;
        ListNode beforeEnd=null;
        ListNode afterStart=null;
        ListNode afterEnd=null;
        ListNode cur=head;
        while(cur!=null){
            if(cur.val<x){
                if(beforeStart==null){
                    beforeStart=beforeEnd=cur;
                }else{
                    beforeEnd.next=cur;
                    beforeEnd=beforeEnd.next;
                }
            }else{
                if(afterStart==null){
                    afterStart=afterEnd=cur;
                }else{
                    afterEnd.next=cur;
                    afterEnd=afterEnd.next;
                }
            }
            cur=cur.next;
        }
        if(beforeStart==null){
            return afterStart;
        }
        beforeEnd.next=afterStart;
        if(afterStart!=null){
            afterEnd.next=null;
        }
        return beforeStart;
    }
    //判断一个链表是否是回文结构；
    public boolean returnListNode(){
        if(head==null){
            return true;
        }
        //1.找中间节点；
        ListNode fast=head;
        ListNode slow=head;
    while(fast!=null&&fast.next!=null){
        fast=fast.next.next;
        slow=slow.next;
    }
    //2.反转中间节点后的节点；
    ListNode cur=slow.next;
    while(cur!=null){
        ListNode curN=cur.next;
        cur.next=slow;
        slow=cur;
        cur=curN;
    }
    //3,判断是否是回文结构；
        while(slow!=head){
            if(head.val!=slow.val){
                return false;
            }
            slow=slow.next;
            head=head.next;
            if(head.next==slow){
                return true;
            }
        }
    return true;
    }
    //判读一个单链表是否有环；
    public boolean ListNodeLoop(){
        ListNode fast=head;
        ListNode slow=head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow){
                return true ;
            }
        }
        return false;
    }
    //判断一个单链表是否有环，返回相遇后的第一个结点；
    public ListNode ListNodeLoopKey(){
        ListNode fast=head;
        ListNode slow=head;
        while(fast!=null&&fast.next!=null){
            fast=fast.next.next;
            slow=slow.next;
            if(fast==slow){
                break;
            }
        }
        if(fast==null||fast.next==null){
            return null;
        }
        fast=head;
        while(fast!=null){
            fast=fast.next;
            slow=slow.next;
        }
        return slow;
    }
    //合并两个阈值有序的单链表；
    public ListNode addListNode(ListNode list1,ListNode list2){
        ListNode newHead=new ListNode(-1);
        ListNode tmp=newHead;
        while(list1!=null&&list2!=null){
            if(list1.val< list2.val){
                tmp.next=list1;
                list1=list1.next;
                tmp=tmp.next;
            }else{
                tmp.next=list2;
                list2=list2.next;
                tmp=tmp.next;
            }
        }
        if(list1!=null){
            tmp.next=list1;
        }
        if(list2!=null){
            tmp.next=list2;
        }
        return newHead.next;
    }
    //
    // 输⼊两个链表,找出它们的第⼀个公共结点。
    public ListNode findFirstListNode(ListNode headA,ListNode headB){
        int lenA=0;
        int lenB=0;
        ListNode pl=headA;
        ListNode ps=headB;
        while(pl!=null){
            lenA++;
            pl=pl.next;
        }
        pl=headA;
        while(ps!=null){
            lenB++;
            ps=ps.next;
        }
        ps=headB;
        int len=lenA-lenB;
        if(len<0){
            pl=headB;
            ps=headA;
            len=lenB-lenA;
        }
        while(len!=0){
            pl=pl.next;
        }
        while(pl!=ps){
            pl=pl.next;
            ps=ps.next;
        }
        if(pl==null){
            return null;
        }
        return pl;
    }
}
